package com.chj.leetcode.tijie350to400;

public class Code377_CombinationSumIv {
	public static int combinationSum4(int[] nums, int target) {
		if (target == 0) {
			return 1;
		}
		int res = 0;
		for (int i = 0; i < nums.length; i++) {
			if (target >= nums[i]) {
				res += combinationSum4(nums, target - nums[i]);
			}
		}
		return res;
	}

	public static int combinationSum4Dp(int[] nums, int target) {
		int[] dp = new int[target + 1];
//		if (target == 0) {
//			return 1;
//		}
		dp[0] = 1;
//		int res = 0;
		for (int i = 1; i < dp.length; i++) {
			for (int j = 0; j < nums.length; j++) {
				if (i >= nums[j]) {
//				res += combinationSum4(nums, target - nums[i]);
					dp[i] += dp[i - nums[j]];
				}
			}
		}
		return dp[target];
	}

	public static void main(String[] args) {
		int[] nums = { 2, 1, 3 };
		int target = 35;
		System.out.println(combinationSum4(nums, target));
		System.out.println(combinationSum4Dp(nums, target));
	}
}
